
const int MAXNODE = 13000010;
const int MAXN = 100010;
const int RE = 100000000;

struct node
{
	node*c[2];
	// must maintain
	int siz;
	// data-related parameters
	int len;
	// mark
	int add;

	void clear(int _siz);
} b[MAXNODE], *emp, *stk;

void node::clear(int _siz)
{
	c[0]=c[1]=emp;
	siz=_siz;
	len=0;
	add=0;
}

node*newnode(int siz)
{
	stk->clear(siz);
	return stk++;
}

node*ins(node*x,int d)
{
	if (!d || x==emp) return x;
	node*ret=newnode(x->siz);
	*ret=*x;
	ret->add+=d;
	return ret;
}

bool nrand(int l,int r)
{
	bool ret;
	#ifdef __unix__	
		ret=(rand()%(l+r))<l;
	#else
		ret=(((rand()<<15)+rand())%(l+r))>l;
	#endif
	return ret;
}

node*merge(node*l,node*r)
{
	if (l==emp) return r;
	if (r==emp) return l;
	bool dir=nrand(l->siz,r->siz);
	node*ret=newnode(l->siz+r->siz);
	if (!dir)
	{
		ret->c[0]=ins(l->c[0],l->add);
		ret->c[1]=merge(ins(l->c[1],l->add),r);
		ret->len=l->len+l->add;
	} else
	{
		ret->c[0]=merge(l,ins(r->c[0],r->add));
		ret->c[1]=ins(r->c[1],r->add);
		ret->len=r->len+r->add;
	}
	return ret;
}

node*cut(node*x,int lim)
{
	if (!lim)
		return emp;
	if (x->siz<=lim)
		return x;
	if (x->c[0]->siz>=lim)
		return ins(cut(x->c[0],lim),x->add);
	node*ret=newnode(lim);
	ret->len=x->len+x->add;
	ret->c[0]=ins(x->c[0],x->add);
	ret->c[1]=ins(cut(x->c[1],lim-x->c[0]->siz-1),x->add);
	return ret;
}

int findkth(node*now,int k,int add)
{
	if (k>now->siz)
		return -1;
	if (now->c[0]->siz>=k)
		return findkth(now->c[0],k,now->add+add);
	k-=now->c[0]->siz;
	if (k==1)
		return now->len+now->add+add;
	return findkth(now->c[1],k-1,now->add+add);
}
